//给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格 。
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
//
//
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
//
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
//
//
// 示例 1:
//
//
//输入: prices = [1,2,3,0,2]
//输出: 3
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
//
// 示例 2:
//
//
//输入: prices = [1]
//输出: 0
//
//
//
//
// 提示：
//
//
// 1 <= prices.length <= 5000
// 0 <= prices[i] <= 1000
//
// Related Topics 数组 动态规划 👍 1051 👎 0

package leetcode.editor.cn;
@SuppressWarnings("all")
//Java：最佳买卖股票时机含冷冻期
public class 最佳买卖股票时机含冷冻期{
    public static void main(String[] args) {
        Solution solution = new 最佳买卖股票时机含冷冻期().new Solution();
        // TO TEST
    }
    /**
     * 不要关注冷冻期！不要关注冷冻期！不要关注冷冻期！
     * 只关注卖出的那一天！只关注卖出的那一天！只关注卖出的那一天！
     * 题目中定义的“冷冻期”=卖出的那一天的后一天，题目设置冷冻期的意思是，如果昨天卖出了，今天不可买入，那么关键在于哪一天卖出，只要在今天想买入的时候判断一下前一天是不是刚卖出，即可，所以关键的一天其实是卖出的那一天，而不是卖出的后一天
     * <p>
     * 正文：
     * 因为当天卖出股票实际上也是属于“不持有”的状态，那么第i天如果不持有，那这个“不持有”就有了两种状态：
     * 1.本来就不持有，指不是因为当天卖出了才不持有的；
     * 2.第i天因为卖出了股票才变得不持有
     * <p>
     * 而持有股票依旧只有一种状态
     * <p>
     * 所以对于每一天i，都有可能是三种状态：
     * 0.不持股且当天没卖出,定义其最大收益dp[i][0];
     * 1.持股,定义其最大收益dp[i][1]；
     * 2.不持股且当天卖出了，定义其最大收益dp[i][2]；
     * <p>
     * 初始化：
     * dp[0][0]=0;//本来就不持有，啥也没干
     * dp[0][1]=-1*prices[0];//第0天只买入
     * dp[0][2]=0;//可以理解成第0天买入又卖出，那么第0天就是“不持股且当天卖出了”这个状态了，其收益为0，所以初始化为0是合理的
     * <p>
     * 重头戏：
     * <p>
     * 一、第i天不持股且没卖出的状态dp[i][0]，
     * 也就是我没有股票，而且还不是因为我卖了它才没有的，
     * 那换句话说是从i-1天到第i天转移时，它压根就没给我股票！所以i-1天一定也是不持有，
     * 那就是不持有的两种可能：i-1天不持股且当天没有卖出dp[i-1][0]；
     * i-1天不持股但是当天卖出去了dp[i-1][2]；
     * 所以： dp[i][0]=max(dp[i-1][0],dp[i-1][2])
     * <p>
     * 二、第i天持股dp[i][1]，今天我持股，来自两种可能：
     * 1、要么是昨天我就持股，今天继承昨天的，也就是dp[i-1][1]，这种可能很好理解；
     * 2、要么：是昨天我不持股，今天我买入的，但前提是昨天我一定没卖！因为如果昨天我卖了，那么今天我不能交易！也就是题目中所谓“冷冻期”的含义，只有昨天是“不持股且当天没卖出”这个状态，我今天才能买入！所以是dp[i-1][0]-p[i]
     * 所以： dp[i][1]=max(dp[i-1][1],dp[i-1][0]-p[i])
     * <p>
     * 三、i天不持股且当天卖出了，这种就简单了，那就是说昨天我一定是持股的，要不然我今天拿什么卖啊，而持股只有一种状态，昨天持股的收益加上今天卖出得到的新收益，就是dp[i-1][1]+p[i]啦
     * 所以：dp[i][2]=dp[i-1][1]+p[i]
     * <p>
     * 总结：最后一天的最大收益有两种可能，而且一定是“不持有”状态下的两种可能，把这两种“不持有”比较一下大小，返回即可
     * <p>
     * 作者：jin-ai-yi
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/fei-zhuang-tai-ji-de-dpjiang-jie-chao-ji-tong-su-y/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxProfit(int[] prices) {

        int n = prices.length;
        if (n <= 1) return 0;


        int[][] dp = new int[n][3];
        dp[0][0] = 0;
        dp[0][1] = -1 * prices[0];
        dp[0][2] = 0;


        for (int i = 1; i < n; i++) {//从[1]...[n-1]
            //原本就不持股
            // 1. i-1天也不持股
            // 2. i-1卖出
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);

            //持有股份
            // 1.  继承i-1天持有的股份
            // 2.  第i天买入股份，意味着i-1天本就不持有股份
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

            //不持有股份，卖出了i-1天持有的股份
            dp[i][2] = dp[i - 1][1] + prices[i];

        }
        // 利润最大化，必须卖出股份
        return Math.max(dp[n - 1][0], dp[n - 1][2]);

    }
}
//leetcode submit region end(Prohibit modification and deletion)


}
